package com.dubious.interview.euler;

import static com.dubious.interview.euler.Utilities.findMax;

import java.util.LinkedList;
import java.util.List;

import org.joda.time.DateTime;

public class Problem4 {

    /**
     * A palindromic number reads the same both ways. The largest palindrome made from the product
     * of two 2-digit numbers is 9009 = 91 99.
     * 
     * Find the largest palindrome made from the product of two 3-digit numbers.
     * 
     * @param args
     */
    public static void main(String[] args) {
        // there are, at most, 900^2 = 810,000 numbers that are the product of two 3 digit numbers
        // we could brute force this:
        // calculate all products of two 3-digit numbers, sort, and find the largest
        System.out.println("Start Time: " + new DateTime());

        List<Long> palindromes = new LinkedList<Long>();
        for (int i = 100; i < 999; i++) {
            for (int j = 100; j < 999; j++) {
                long product = i * j;
                if (isPalindrome(product)) {
                    palindromes.add(product);
                }
            }
        }

        System.out.println("Maximum value palindrome that is product of 2 3-character numbers: "
                + findMax(palindromes));
        System.out.println("End Time: " + new DateTime());
    }

    private static boolean isPalindrome(Long value) {
        String valueString = Long.toString(value);
        for (int i = 0; i < valueString.length() / 2 + 1; i++) {
            if (valueString.charAt(i) != valueString.charAt(valueString.length() - i - 1)) {
                return false;
            }
        }

        return true;
    }
}
